Many optimization problems can be modeled as weighted directed graphs. Graphs are visual and mathematical representations of vertices or nodes which are connected together by edges. A directed graph is where the edges between nodes have a particular direction or flow and is also known as a flow network. A weighted directed graph is a directed graph where each edge is also given a weight. The weight represents a cost for using a particular edge over another. Such graphs are also known as weighted flow networks. Weighted flow networks have found use in problems of logistics, which deal with the movement or flow of goods or objects from one node to another. Such problems include finding a shortest path between two nodes, and have found practical use in optimizing the flow of cars in traffic and information over a network, for example.
Reference is now made to FIG. 1, which is a schematic illustration of a weighted flow network, generally referenced 10, as is known in the prior art. Weighted flow network 10 includes a plurality of vertices 12, 14, 16A, 16B, 16C, 16D, 16E, 16F and 16G. Vertex 12, labeled with an ‘A’, represents a point of departure, source, start or initial start position. Vertex 14, labeled with a ‘B’, represents a destination, target, end or end position. Vertices 16A-16G, labeled with numbers ‘1’ to ‘7’, represent intermediate nodes via which a good, an object, information and the like can travel from vertex A to vertex B. As shown in weighted flow network 10, not every vertex is connected to every other vertex. Each connection between two vertices is referred to as an edge. Vertex A is connected with vertices 1, 2 and 3 via edges 18A, 18B and 18C respectively. Vertex 1 is connected with vertex 5 via an edge 18E, vertex 2 is connected with vertex 4 via an edge 18D, vertex 3 is connected with vertices 4 and 5 via edges 18F and 18G respectively, vertex 4 is connected with vertex 6 via an edge 18H, vertex 5 is connected with vertex 7 via an edge 18J, vertex 6 is connected with vertices 7 and B via edges 18I and 18K respectively and vertex 7 is connected with vertex B via an edge 18L.
The connections between the vertices show the various paths via which a good or object can travel from vertex A to vertex B. FIG. 1 shows two possible paths, a first path 20, labeled ‘PATH 1’ and a second path 22, labeled ‘PATH 2’. It is obvious that other paths exist, however for the purposes of explanation only two paths are shown in FIG. 1. First path 20 goes from vertex A to vertex 3, vertex 3 to vertex 4, vertex 4 to vertex 6, vertex 6 to vertex 7 and vertex 7 to vertex B. Second path 22 goes from vertex A to vertex 1, vertex 1 to vertex 5, vertex 5 to vertex 7 and vertex 7 to vertex B. As shown in FIG. 1, weighted flow network 10 also includes a plurality of weights associated with each edge. Edge 18A has a weight of 1.6, edge 18B has a weight of 3.9, edge 18C has a weight of 4.5, edge 18D has a weight of 8.7, edge 18E has a weight of 6.8, edge 18F has a weight of 1.1, edge 18G has a weight of 4.7, edge 18H has a weight of 3.5, edge 18I has a weight of 5.6, edge 18J has a weight of 3.8, edge 18K has a weight of 6.1 and edge 18L has a weight of 6.3. Each weight represents a cost or metric associated with using a particular edge. For example, if weighted flow network 10 were used as a model of the flow of current, each weight might represent a capacity of current a particular edge can accommodate, therefore edges with higher weights represents edges that can accommodate more capacity for current. Alternatively, if weighted flow network 10 were used as a model of the flow of traffic, each weight might represent a distance between vertices, therefore edges with higher weights represents edges which are longer in distance. Using the associated weights with each edge, the total cost of a path can be determined. For example, the total cost of first path 20 is 21.0, whereas the total cost of second path 22 is 18.5. An optimization algorithm, such as known shortest path (herein abbreviated SP) algorithms, can be used to determine the shortest path between vertex A and vertex B. Phrased otherwise, the shortest path may be the path with lowest cost, such as in the case that the edges in weighted flow network 10 represent the distance between vertices. However the same SP algorithms can also be used to find the path with the highest cost, such as in the case that the edges represent capacity for current. In such a case, the weights for each edge could be multiplied by −1 and thus a ‘shortest’ path can be found using such SP algorithms, even though that shortest path (e.g., of resistance) represents one with the highest capacity for current. Such SP algorithms usually determine all possible paths between a start vertex and an end vertex and then determine the cost of each possible path. Depending on how the optimization is phrased, the path with the lowest cost or highest cost is returned as the optimal path to be taken to go from vertex A to vertex B.
The weighted flow network shown in FIG. 1 is used by many computer programs and mobile applications to determine a shortest path between two vertices. A particular known example is in determining the shortest path for driving from a point of departure or a source to a destination within minimal time. Examples of programs and applications that can determine such shortest paths include Google® Maps, Waze, MapQuest®, Sygic® and the like. Reference is now made to FIGS. 2A-2F, which are schematic illustrations of a weighted flow network modeling a shortest path between a point of departure and a destination over a plurality of iterations, generally referenced 40-40′″″, as is known in the prior art. In general, similar reference numerals are used throughout FIGS. 2A-2F to show similar elements in each of those figures, with an apostrophe symbol appended to a reference numeral to differentiate similar elements in different figures. Each of FIGS. 2A-2F shows the determination of a shortest path between a vertex A, representing a point of departure or source and a vertex B, representing a destination, at different iterations of a SP algorithm. To keep the figures from being too cluttered, a simplified weighted flow network between vertices A and B is shown including only three vertices and six edges, it being understood that real world representations of such problems usually include tens if not hundreds of vertices and edges.
Reference is now made to FIG. 2A, which includes a point of departure vertex 42, shown as a vertex A and a destination vertex 44, shown as a vertex B. Vertices 42 and 44 represent two different cities, such as Tel-Aviv and Jerusalem. FIG. 2A models the shortest path problem of a driver wanting to leave Tel-Aviv and arrive in Jerusalem in minimal time. Vertex A and vertex B are connected via a plurality of intermediate vertices 46A, 46B and 46C and edges 48A, 48B, 48C, 48D, 48E and 48F. Vertices 46A, 46B and 46C are shown in FIG. 2A as vertices ‘1’, ‘2’ and ‘3’. Edge 48A connects vertex A to vertex 1, edge 48B connects vertex A to vertex 3, edge 48C connects vertex 1 to vertex 2, edge 48D connects vertex 3 to vertex 2, edge 48E connects vertex 3 to vertex B and edge 48F connects vertex 2 to vertex B. Each of edges 48A-48F represents major roads and highways between Tel-Aviv and Jerusalem, with vertices 46A, 46B and 46C representing major intersections of those roads and highways. As shown in FIG. 2A, each edge has an associated weight, the weight representing the time required to travel on a particular road or highway at a given time. The time required can be the distance between two vertices divided by the average speed a car can travel between two vertices based on the traffic and congestion of that particular road or highway at a given time. Edge 48A has a weight of 12 minutes (abbreviated min in the figures), edge 48B has a weight of 32 minutes, edge 48C has a weight of 18 minutes, edge 48D has a weight of 20 minutes, edge 48E has a weight of 41 minutes and edge 48F has a weight of 15 minutes. An iteration marker 52, using the variable ‘k’, is used to show the iteration during which a known SP algorithm is used to determine the shortest path between Tel-Aviv and Jerusalem. Since the weights shown in FIG. 2A represent the amount of time required for a car to travel down a road or highway, the shortest path between Tel-Aviv and Jerusalem is represented as the path through which the car travels at the minimal amount of time. Phrased differently, this is equivalent to the shortest travel time between the two cities.
During a first iteration, where k=1, a shortest path 50, labeled as ‘SP’, is shown. Shortest path 50 is from vertex A to vertex 1, vertex 1 to vertex 2 and vertex 2 to vertex B. FIG. 2A may graphically represent a user query submitted to a program or application such as Waze or Sygic® requesting how to drive from Tel-Aviv to Jerusalem in the shortest amount of time. Reference is now made to FIG. 2B, which shows the same weighted flow network as in FIG. 2A, except with an iteration marker 52′ now showing k=2. FIG. 2B may thus graphically represent another user query to the same program or application, submitted soon after the user query of FIG. 2A was submitted, again requesting how to drive from Tel-Aviv to Jerusalem in the shortest amount of time. As shown, the weights of edges 48′A-48′F are identical to the weights of edges 48A-48F (FIG. 2A), as perhaps not much time has elapsed between the user query of FIG. 2A and the user query of FIG. 2B. As shown a shortest path 50′ is shown, from vertex A to vertex 1, vertex 1 to vertex 2 and vertex 2 to vertex B. Therefore the user who submitted the query as graphically shown in FIG. 2B would take the same route as the user who submitted the query as graphically shown in FIG. 2A. It is noted that the weights in FIGS. 2A and 2B may be provided to the algorithm determining the shortest path between vertex A and vertex B by another program or application (not shown).
Reference is now made to FIG. 2C, which shows the same weighted flow network as in FIGS. 2A and 2B, except with an iteration marker 52″ now showing k=3. FIG. 2C may thus graphically represent a further user query to the same program or application, submitted soon after the user queries of FIGS. 2A and 2B were submitted, again requesting how to drive from Tel-Aviv to Jerusalem in the shortest amount of time. As shown in FIG. 2C, the weights of some of the edges in a weighted flow network 40″ have changed as compared to FIGS. 2A and 2B. The weights of edges 48″B, 48″C, 48″D, 48″E and 48″F have all changed as traffic flow is a dynamic matter and is influenced by the choices drivers make in terms of how to drive from their respective points of departure to their respective destinations. The weight of edge 48″B is now 30 minutes as compared to edge 48′B (FIG. 2B) which was 32 minutes. The weight of edge 48″C is now 20 minutes as compared to edge 48′C (FIG. 2B) which was 18 minutes. The weight of edge 48″D is now 26 minutes as compared to edge 48′D (FIG. 2B) which was 20 minutes. The weight of edge 48″E is now 36 minutes as compared to edge 48′E (FIG. 2B) which was 41 minutes. The weight of edge 48″F is now 18 minutes as compared to edge 48′F (FIG. 2B) which was 15 minutes. As shown, the weights of some of the edges in FIG. 2C have increased as compared to FIGS. 2A and 2B, such as edges 48″B and 48″E, whereas the weights of other edges have decreased as compared to FIGS. 2A and 2B, such as edges 48″C, 48″D and 48″F. In FIG. 2C, a shortest path 50″ is shown, going from vertex A to vertex 1, vertex 1 to vertex 2 and vertex 2 to vertex B. Even though the weights of the edges have changed, the determined shortest path in the query illustrated in FIG. 2C is the same as the determined shortest path in FIGS. 2A and 2B.
Reference is now made to FIG. 2D, which shows the same weighted flow network as in FIGS. 2A-2C, except with an iteration marker 52′″ now showing k=1000. FIG. 2D may thus graphically represent another user query to the same program or application, submitted significantly after the user queries of FIGS. 2A-2C were submitted, again requesting how to drive from Tel-Aviv to Jerusalem in the shortest amount of time. As shown in FIG. 2D, all the weights of the edges in a weighted flow network 40′″ have changed as compared to FIGS. 2A-2C. In addition, a shortest path 50′″ determined is now completely different than the determined shortest paths in FIGS. 2A-2C. Shortest path 50′″ is from vertex A to vertex 3 and from vertex 3 to vertex B.
Reference is now made to FIG. 2E, which shows the same weighted flow network as in FIGS. 2A-2D, except with an iteration marker 52″″ now showing k=2500. FIG. 2E may thus graphically represent another user query to the same program or application, submitted significantly after the user query of FIG. 2D was submitted, again requesting how to drive from Tel-Aviv to Jerusalem in the shortest amount of time. As shown in FIG. 2E, all the weights of the edges in a weighted flow network 40″″ have changed again as compared to FIGS. 2A-2D. In addition, a shortest path 50″″ determined is now completely different than the determined shortest path in FIG. 2D however it is the same shortest path as determined in FIGS. 2A-2C. Shortest path 50″″ is from vertex A to vertex 1, vertex 1 to vertex 2 and vertex 2 to vertex B.
Reference is now made to FIG. 2F, which shows the same weighted flow network as in FIGS. 2A-2E, except with an iteration marker 52′″″ now showing k=5000. FIG. 2F may thus graphically represent another user query to the same program or application, again submitted significantly after the user query of FIG. 2E was submitted, again requesting how to drive from Tel-Aviv to Jerusalem in the shortest amount of time. As shown in FIG. 2F, all the weights of the edges in a weighted flow network 40′″″ have changed again as compared to FIGS. 2A-2E. In addition, a shortest path 50′″″ determined is now completely different than the determined shortest paths of any of FIGS. 2A-2E. Shortest path 50′″″ is from vertex A to vertex 3, vertex 3 to vertex 2 and vertex 2 to vertex B.
As shown above in FIGS. 2A-2F, according to the prior art, each time a shortest path is determined in a weighted flow network, a determination is made based on the current and most up-to-date weights of each edge in the weighted flow network. Many factors can influence the weight of an edge, such as the time of day, the number of drivers on a particular road, the familiarity of a particular road to a given driver and the likelihood that the driver will drive on that particular road, and the like. In a dynamic weighed flow network, such as shown above in FIGS. 2A-2F, the weights dynamically change over time and thus the determined shortest path from vertex A to vertex B will change over time. As shown above, a first user (k=1) of an application such as Waze or Sygic® may be directed to take shortest path 50 (FIG. 2A) whereas user five thousand (k=5000) of such programs may be directed to take shortest path 50′″″ (FIG. 2F) which is very different than shortest path 50. Thus each user of such programs is given an optimized shortest path for that user at a given time period.
Looking over time, from k=1 until k=5000, the load on the weighted flow networks of FIGS. 2A-2F constantly changes and fluctuates. In general, the load represents how many things, goods or objects can travel at any given time in a flow network as well as through which paths in the flow network they can travel down. The load (not shown) in FIGS. 2A-2F thus represents how many cars can travel on the various possible paths between vertices A and B. Loads can be classified on a spectrum of being balanced on one side and unbalanced on the other. Unbalanced loads in flow networks occur when certain paths carry a substantial portion of the total load in the flow network whereas other paths carry a minimal portion of the total load in the flow network. Unbalanced loads in a weighted flow network can thus be seen over time when the shortest path from a start vertex to an end vertex continually changes, as shown above in FIGS. 2C-2F. Balanced loads in flow networks occur when the total flow is substantially evenly spread out and balanced between the various possible paths from a start vertex to an end vertex. As shown above, the decisions which users of an SP algorithm make in weighted flow networks tend to generate unbalanced loads in those weighted flow networks. Since users usually choose the shortest path at a given moment, such path decisions eventually cause an imbalance in the weighted flow network.
Methods and systems for balancing the load in weighted flow networks are known in the art. US Patent Application Publication No. 2014/0269268 to Rao, entitled “Providing network-wide enhanced load balancing” is directed to a method and apparatus for providing network-wide enhanced load balancing. In an embodiment, a first message comprising a first value and an address is generated. The first message is transmitted to a first node via a first communication link. A second message comprising a second value and the address is generated. The first and second values are unequal. The second message is transmitted to the first node via a second communication link. Packets are received, wherein each of the packets comprises the address. A first percentage of the packets are forwarded to a first device via the first communication link, wherein the first percentage is proportional to the first value. A second percentage of the packets are forwarded to a second device via the second communication link, wherein the second percentage is proportional to the second value.
US Patent Application No. 2014/0280969 to Wood et al., entitled “Load balancer and related techniques” is directed to a system for balancing network traffic among virtual machines. The system includes a first virtual machine executed by a first physical server connected to a physical network and a second virtual machine executed by a second physical server connected to the physical network. A gateway device is configured to route network traffic through the physical network to and from the first and second virtual machines. A load balancer module is executed by the gateway device. The load balancer module is configured to at least partially decode the network traffic to identify a destination address of the network traffic and to determine if the destination address is the address of a load-balanced virtual machine. The load balancer module is also configured to route the network traffic to a destination virtual machine according to a load-balancing scheme if the destination address is the address of a load-balanced virtual machine.
US Patent Application Publication No. 2014/0379938 to Bosch et al., entitled “Hierarchical load balancing in a network environment” is directed to a method for load balancing in a network environment. The method includes the operations of receiving a packet from a first stage load-balancer in a network environment, where the packet is forwarded from the first stage load-balancer to one of a plurality of second stage load-balancers in the network according to a hash based forwarding scheme, and routing the packet from the second stage load-balancer to one of a plurality of servers in the network according to a per-session routing scheme. The per-session routing scheme includes retrieving a session routing state from a distributed hash table in the network. The hash based forwarding scheme can include equal cost multi path routing. The session routing state can include an association between a next hop for the packet and the packet's 5-tuple representing a session to which the packet belongs.